package com.wsy.wsyojcodesandbox.utils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Trie {
    private TrieNode root;

    public Trie(List<String> blackList) {
        root = new TrieNode();
        build(blackList);
    }

    private void build(List<String> blackList) {
        for(String str: blackList) {
            TrieNode cur = root;
            for(char c: str.toCharArray()) {
                if(!cur.next.containsKey(c)) {
                    cur.next.put(c, new TrieNode());
                }
                cur = cur.next.get(c);
            }
            cur.end = true;
            cur.word = str;
        }
    }

    public String containsBlacklistWord(String code) {
        char[] codes = code.toCharArray();
        for(int i = 0; i < codes.length; i++) {
            TrieNode cur = root;
            int j = i;
            while(j < codes.length) {
                if (cur.next.containsKey(codes[j])) {
                    cur = cur.next.get(codes[j]);
                }else {
                    break;
                }
                j++;
            }
            if(cur.end) {
                return cur.word;
            }
        }
        return null;
    }

    public static class TrieNode {
        private Map<Character, TrieNode> next;
        private boolean end;
        private String word;

        public TrieNode() {
            next = new HashMap<>();
        }
    }
}
